package 左哥算法.ch14单调栈;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

public class Ch01 {

    /**
     * ch01：找到每个元素两侧比自己更大的值（离自己最近的）
     */
    @Test
    public void test01(){
        int[][] nums = nearbyGreaterElements(new int[]{5,4,3,6,1,2,0,7});
        for (int i = 0; i < nums.length; i++) {
            System.out.println(i+":"+Arrays.toString(nums[i]));
        }
    }
    /**
     * ch01：找到每个元素两侧比自己更大的值（离自己最近的），数组不会出现重复值的情况
     * 思路：
     *  准备一个栈单调栈，（下方元素总比上面的元素大）
     *  将数组中的元素尝试入栈
     *      如果当前节点比栈顶元素小，则入栈
     *      如果当前元素比栈顶元素大，则当前元素为栈顶元素的右侧更大值，栈顶下方的元素为栈顶元素左侧的更大值。
     *          将栈顶元素出栈，再用尝试当前元素入栈
     */
    public int[][] nearbyGreaterElements(int[] nums){
        int[][] res=new int[nums.length][2];    //0位置代表左侧更大值，1位置表示右侧更大值
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            if (stack.isEmpty()||nums[stack.peek()]>nums[i]){
                stack.push(i);
            }else {
                Integer index = stack.pop();
                res[index][0]=stack.isEmpty()?-1:nums[stack.peek()];
                res[index][1]=nums[i];
                i--;
            }
        }
        while (!stack.isEmpty()){
            Integer index = stack.pop();
            res[index][0]=stack.isEmpty()?-1:nums[stack.peek()];
            res[index][1]=-1;   //右侧没有更大值
        }

        return res;
    }

    /**
     * ch02:子数组最小乘积的最大值
     */
    @Test
    public void tset02(){
        int max = maxSumMinProduct(new int[]{1,1,3,2,2,2,1,5,1,5});
        System.out.println(max);
    }
    /**
     * ch02:子数组最小乘积的最大值
     *  一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。返回子数组（连续的数组）和其最小值乘积的最大值
     * 暴力思路：记录下每个位置作为最小值，其组成的数组能取到的最小乘积，然后对对所有最小乘积进行比较
     * 单调栈思路：每个位置组成的数组，其左右位置都要比自己大，如果比自己小，则数组确定.（也就是找左右两侧距离自己最近的更小值）
     *      1.准备一个栈单调递增栈（下方元素比上方元素小）。
     */
    public int maxSumMinProduct(int[] nums) {
//        int[][] res=new int[nums.length][2];    //0位置代表左侧更小值下标，1位置表示右侧更小值下标
        long max=-1;
        Stack<LinkedList<Integer>> stack=new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            if (stack.isEmpty()||nums[stack.peek().getFirst()]<nums[i]) {
                LinkedList<Integer> list = new LinkedList<>();
                list.addFirst(i);
                stack.push(list);
            }else if (nums[stack.peek().getFirst()]==nums[i]){
                stack.peek().addLast(i);
            }else {
                LinkedList<Integer> list = stack.pop();
                long res=0;
                for (int l=stack.isEmpty()?0:stack.peek().peekLast()+1; l < i; l++) {
                    res+=nums[l];
                }
                max=Math.max(res*nums[list.peekFirst()],max);
                i--;
            }
        }
        while (!stack.isEmpty()){   //右侧没有比自己更小的
            LinkedList<Integer> list = stack.pop();
            long res=0;
            for (int l=stack.isEmpty()?0:stack.peek().peekLast()+1; l <nums.length; l++) {
                res+=nums[l];
            }
            max=Math.max(res*nums[list.peekFirst()],max);
        }
        return (int)max;
    }
}
